package experiment5;

/**
 * @author mazouri
 * @create 2021-11-18 10:40
 */
public class ReversePairs {
    private int count;
    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if       (i > mid)           a[k] = aux[j++];
            else if  (j > hi)            a[k] = aux[i++];
            else if  (aux[j] < aux[i])   { a[k] = aux[j++]; count += (mid - i + 1); }
            else                         a[k] = aux[i++];
        }
    }

    private void sort(int[] a, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public static void main(String[] args) {
        int[] arr = {7,5,6,4};
        int[] aux = new int[arr.length];
        ReversePairs rp = new ReversePairs();
        rp.sort(arr,aux,0,arr.length-1);
        System.out.println(rp.count);
    }
}
